package leetcode101.double_pointer;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code7
 * @Description 75. Sort Colors
 * Given an array nums with n objects colored red, white, or blue,
 * leetcode101.sort them in-place so that objects of the same color are adjacent,
 * with the colors in the order red, white, and blue.
 *
 * We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
 *
 *  
 *
 * Example 1:
 *
 * Input: nums = [2,0,2,1,1,0]
 * Output: [0,0,1,1,2,2]
 * Example 2:
 *
 * Input: nums = [2,0,1]
 * Output: [0,1,2]
 * Example 3:
 *
 * Input: nums = [0]
 * Output: [0]
 * Example 4:
 *
 * Input: nums = [1]
 * Output: [1]
 *  
 *
 * Constraints:
 *
 * n == nums.length
 * 1 <= n <= 300
 * nums[i] is 0, 1, or 2.
 *  
 *
 * Follow up:
 *
 * Could you solve this problem without using the library's leetcode101.sort function?
 * Could you come up with a one-pass algorithm using only O(1) constant space?
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-30 10:51
 */
public class Code7 {

    public static void main(String[] args) {
        int[] nums = new int[] {2, 1, 2};
        sortColors(nums);
    }

    public static void sortColors(int[] nums) {
        int p0 = 0, p2 = nums.length - 1, pointer = 0;
        while (pointer <= p2) {
            if (nums[pointer] == 1) {
                pointer++;
            } else if (nums[pointer] == 0) {
                swap(nums, p0, pointer);
                pointer++;
                p0++;
            } else {
                swap(nums, p2, pointer);
                p2--;
            }
        }
    }

    public static void swap(int[] nums, int pos1, int pos2) {
        int temp = nums[pos1];
        nums[pos1] = nums[pos2];
        nums[pos2] = temp;
    }
}
